# Euler totient function and its basic formulas.
Define for each positive integer $n$ the number $\varphi(n)$ to be $$
\varphi(n) = \#\{k \in [n]: \gcd(n,k)=1\},
$$the number of positive integers no greater than $n$ that are coprime with $n$. Here $[n]$ denotes the set $\{1,2,\ldots,n\}$.
A small table of $\phi(n)$ goes as follows,$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline
\varphi(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4
\end{array}
$$
What we like to do first is establish a main formula for computing $\varphi(n)$, where $$
\varphi(n) = n \prod_{p|n}\left( 1-\frac{1}{p} \right)
$$where $p$ is prime; as well as the multiplicative property $$
\varphi(ab) = \varphi(a)\varphi(b)
$$whenever $a,b$ coprime.
## Simple case when prime power.
Note when $p$ is a prime number, then the integers $1,2,\ldots, p-1$ are all coprime with $p$. So we have $$
\varphi (p) = p-1
$$when $p$ prime.
Now, when we have a prime power $p^{k}$, the integers of the form $kp$ for $k\in \{1,2,\ldots,p^{k-1}\}$ are the only integers among $[p^{k}]$ that shares a nontrivial factor with $p^{k}$. Hence $$
\varphi(p^{k}) = p^{k} - p^{k-1}.
$$
## Some explorations.
Let us say $n = p^{a}q^{b}$, where $p,q$ are some distinct primes, so we move on to two distinct prime factors. Then among all the positive integers in $[n]$, we need to avoid all multiples of $p$ and all multiples of $q$ to remain relatively prime with $n$.
Well, all numbers of the form $k p$ where $k=1,\ldots, \frac{n}{p}$ share a common factor $p$ with $n$; while all numbers of the form $kq$ where $k=1,\ldots, \frac{n}{q}$ share a common factor $q$ with $n$. But these two lists may have double counted, precisely those of the form $kpq$ where $k=1,\ldots, \frac{n}{pq}$.
So by inclusion-exclusion, we see that $\varphi(p^{a}q^{b})$ ought to equal to $$
n- \frac{n}{p} - \frac{n}{q} + \frac{n}{pq}.
$$
Observe algebraically this is just $$
n \left( 1 - \frac{1}{p} \right) \left( 1-\frac{1}{q} \right)
$$
Aha, now we see where our formula is taking shape!
## General case.
Suppose now $n=p_{1}^{a_{1}}p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$ with some $k$ distinct prime factors $p_{1},\ldots,p_{k}$.
Denote the set $A_{p}$ to be the set of numbers in $[n]$ that has a factor of $p$. Then $|A_{p}| = \frac{n}{p}$.
Note then the intersection $|A_{p} \cap A_{q}|$ has size $\frac{n}{pq}$, for $p,q$ distinct prime factors of $n$.
And in general, $$
|A_{p_{1}} \cap A_{p_{2}} \cap \cdots \cap A_{p_{\ell}}| = \frac{n}{p_{1}p_{2}\cdots p_{\ell}}
$$
By inclusion-exclusion, we see that $$
\varphi(n) = n-\sum_{p} \frac{n}{p} + \sum_{p_{1} < p_{2}} \frac{n}{p_{1} p_{2}} -\sum_{p_{1} < p_{2} < p_{3}} \frac{n}{p_{1}p_{2}p_{3}} + \cdots + (-1)^{k} \frac{n}{p_{1}p_{2}\cdots p_{k}}
$$where the sums are over distinct prime factors of $n$. Algebraically, we get $$
\varphi(n) = n \left( 1- \frac{1}{p_{1}} \right)\left( 1- \frac{1}{p_{2}} \right) \cdots \left( 1- \frac{1}{p_{k}} \right) = n \sum_{p}\left( 1- \frac{1}{p} \right)
$$as claimed.
## Multiplicative property.
Now suppose $m$ and $n$ are relatively prime, where $m = p_{1}^{a_{1}}\cdots p_{k}^{a_{k}}$ and $n = q_{1}^{b_{1}}\cdots q_{\ell}^{b_{\ell}}$, where $p_{i}$ and $q_{j}$ are distinct primes. Then now it is clear that $$
\varphi(mn) = mn \prod_{p|(mn)} \left( 1- \frac{1}{p} \right) = m \prod_{p|m} \left( 1- \frac{1}{p} \right) \cdot n\prod_{q|n}\left( 1 - \frac{1}{q} \right) = \varphi(m)\varphi(n).
$$
Now, what if $m$ and $n$ has common divisor greater than $1$? Say $\gcd(m,n)=d > 1$.
Say in this case, $p_{i}$'s are primes that are exclusively prime factors of $m$, but not $n$; and $q_{j}$'s are primes that are exclusively prime factors of $n$, but not $m$; and let $r_{k}$'s be prime factors of $d = \gcd(m,n)$. Then $$
\begin{align*}
&\varphi(mn)\\ &= mn \prod_{p_{i}}\left( 1- \frac{1}{p_{i}} \right)\prod_{q_{i}}\left( 1- \frac{1}{q_{i}} \right)\prod_{r_{i}}\left( 1- \frac{1}{r_{i}} \right) \\
&= m \prod_{p_{i}}\left( 1- \frac{1}{p_{i}} \right)\prod_{r_{i}}\left( 1- \frac{1}{r_{i}} \right)n\prod_{q_{i}}\left( 1- \frac{1}{q_{i}} \right)\prod_{r_{i}}\left( 1- \frac{1}{r_{i}} \right) / \prod_{r_{i}}\left( 1- \frac{1}{r_{i}} \right) \\
& = \varphi(m) \varphi(n) \frac{1}{\prod_{r_{i}}\left( 1- \frac{1}{r_{i}} \right)} \\
&= \varphi(m) \varphi(n) \frac{d}{d\prod_{r_{i}}\left( 1- \frac{1}{r_{i}} \right)}
\end{align*}
$$This gives a more generic multiplicative formula, for any positive integers $m,n$, with $d=\gcd(m,n)$, we have $$
\varphi(mn) = \varphi(m) \varphi(n) \frac{d}{\varphi(d)}.
$$
B / 7 2024